package com.leetcode.algs4.graph;

/**
 * @author Dennis Li
 * @date 2020/6/16 14:40
 */
// 记录连通分量
public class CC {
    private boolean[] marked;
    // 记录顶点所属的连通分量的id
    private int[] id;
    private int count;

    public CC(Graph G) {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        for (int i = 0; i < G.V(); i++) {
            if (!marked[i]) {
                dfs(G, i);
                count++;
            }
        }
    }

    private void dfs(Graph G, int s) {
        marked[s] = true;
        id[s] = count;
        for (int w : G.adj(s)) {
            if (!marked[s]) {
                dfs(G, w);
            }
        }
    }

    public boolean connected(int v, int w){
        // 如果所属的连通分量id相同，则证明v和w相互连通
        return id[v] == id[w];
    }

}
